#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<unordered_map>
#include<vector>
using namespace std;

class Solution {
public:
    pair<int, int> expand(string s, int left, int right)
    {
        while (left >= 0 && right < s.size() && s[left] == s[right])
        {
            --left, ++right;
        }
        return { left + 1,right - 1 };
    }

    string longestPalindrome(string s) {
        int n = s.size();
        int start = 0, end = 0;
        for (int i = 0; i < n; ++i)
        {
            auto [left1, right1] = expand(s, i - 1, i + 1);
            auto [left2, right2] = expand(s, i, i + 1);
            if (right1 - left1 > end - start)
            {
                start = left1;
                end = right1;
            }
            if (right2 - left2 > end - start)
            {
                start = left2;
                end = right2;
            }
        }
        return s.substr(start, end - start + 1);
    }
};

struct linkNode
{
    int key, val;
    linkNode* pre;
    linkNode* next;
    linkNode()
        :key(0)
        , val(0)
        , pre(nullptr)
        , next(nullptr)
    {}
    linkNode(int _key, int _val)
        :key(_key)
        , val(_val)
        , pre(nullptr)
        , next(nullptr)
    {}
};

class LRUCache {
public:
    linkNode* head;
    linkNode* tail;
    unordered_map<int, linkNode*> map;
    int capacity;
    int size;
    LRUCache(int _capacity)
        :capacity(_capacity)
        , size(0)
    {
        head = new linkNode();
        tail = new linkNode();
        head->next = tail;
        tail->next = head;
    }

    int get(int key) {
        if (!map.count(key))
            return -1;

        linkNode* getnode = map[key];
        moveNode(getnode);
        return getnode->val;
    }

    void put(int key, int value) {
        if (map.count(key))
        {
            linkNode* node = map[key];
            node->val = value;
            moveNode(node);
        }
        else
        {
            linkNode* newnode = new linkNode(key, value);
            map[key] = newnode;
            ++size;
            addNode(newnode);
            if (capacity < size)
            {
                linkNode* removed = removeTail();
                map.erase(removed->key);
                delete removed;
                --size;
            }
        }
    }

    void moveNode(linkNode* node)
    {
        removeNode(node);
        addNode(node);
    }

    void removeNode(linkNode* node)
    {
        node->pre->next = node->next;
        node->next->pre = node->pre;
    }

    void addNode(linkNode* node)
    {
        node->pre = head;
        node->next = head->next;
        head->next->pre = node;
        head->next = node;
    }

    linkNode* removeTail()
    {
        linkNode* node = tail->pre;
        removeNode(node);
        return node;
    }
private:
};